package test3;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution6 {

    class TrieNode {
        HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
        public TrieNode() {}
    }

    class Solution {
        public int findMaximumXOR(int[] nums) {
            // Compute length L of max number in a binary representation
            int maxNum = nums[0];
            for(int num : nums) maxNum = Math.max(maxNum, num);
            int L = (Integer.toBinaryString(maxNum)).length();

            // zero left-padding to ensure L bits for each number
            int n = nums.length, bitmask = 1 << L;
            String [] strNums = new String[n];
            for(int i = 0; i < n; ++i) {
                strNums[i] = Integer.toBinaryString(bitmask | nums[i]).substring(1);
            }

            TrieNode trie = new TrieNode();
            int maxXor = 0;
            for (String num : strNums) {
                TrieNode node = trie, xorNode = trie;
                int currXor = 0;
                for (Character bit : num.toCharArray()) {
                    // insert new number in trie
                    if (node.children.containsKey(bit)) {
                        node = node.children.get(bit);
                    } else {
                        TrieNode newNode = new TrieNode();
                        node.children.put(bit, newNode);
                        node = newNode;
                    }

                    // compute max xor of that new number
                    // with all previously inserted
                    Character toggledBit = bit == '1' ? '0' : '1';
                    if (xorNode.children.containsKey(toggledBit)) {
                        currXor = (currXor << 1) | 1;
                        xorNode = xorNode.children.get(toggledBit);
                    } else {
                        currXor = currXor << 1;
                        xorNode = xorNode.children.get(bit);
                    }
                }
                maxXor = Math.max(maxXor, currXor);
            }

            return maxXor;
        }
    }

    public int[][] kClosest(int[][] points, int K) {
        PriorityQueue<Map.Entry<Integer, Integer>> q = new PriorityQueue<>(K, (v1, v2) -> v2.getValue() - v1.getValue());
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < points.length; i++) {
            int stance = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            map.put(i, stance);
        }
        map.entrySet().forEach(entry -> {

            if (q.size() < K) {
                q.add(entry);
            } else if (q.peek().getValue() > entry.getValue()) {
                 q.poll();
                 q.add(entry);
            }
        });

        int[][] res = new int[K][];
        int i = 0;
        while(!q.isEmpty()) {
            res[i] = points[q.poll().getKey()];
            i++;
        }
        return res;
    }

    /*public String frequencySort(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        for (Character c: chars) {

        }

    }*/

    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int WIDTH = 2 * nums[nums.length - 1];

//multiplicity[i] = number of nums[j] == nums[i] (j < i)
        int[] multiplicity = new int[nums.length];
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] == nums[i-1]) {
                multiplicity[i] = 1 + multiplicity[i - 1];
            }
        }

//prefix[v] = number of values <= v
        int[] prefix = new int[WIDTH];
        int left = 0;
        for (int i = 0; i < WIDTH; ++i) {
            while (left < nums.length && nums[left] == i) left++;
            prefix[i] = left;
        }

        int lo = 0;
        int hi = nums[nums.length - 1] - nums[0];
        while (lo < hi) {
            int mi = (lo + hi) / 2;
            int count = 0;
            for (int i = 0; i < nums.length; ++i) {
                count += prefix[nums[i] + mi] - prefix[nums[i]] + multiplicity[i];
            }
//count = number of pairs with distance <= mi
            if (count >= k) hi = mi;
            else lo = mi + 1;
        }
        return lo;
    }



}
